package 动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 动态规划
 * 深度优先搜索
 */
public class Solution131 {

    List<List<String>> result=new ArrayList<>();
    public List<List<String>> partition(String s) {
        if(s==null||s.length()==0){
            return result;
        }
            dp(new ArrayList<>(),s,0);

        return result;
    }

    private void dp(List<String> temp,String s,int start) {
        if (start >= s.length()) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = start+1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (isPalindrome(sub, 0, sub.length() - 1)) {
                temp.add(sub);
                dp(temp, s, i);
                temp.remove(temp.size() - 1);
            }

        }
    }
    private boolean isPalindrome(String str,int start,int end){
        if(start>=end){
            return true;
        }
        if(str.charAt(start)!=str.charAt(end)){
            return false;
        }
        return isPalindrome(str,start+1,end-1);
    }

    @Test
    public void test(){
        List<List<String>> result=partition("abbab");
        System.out.println(result);
    }
}
